package com.yb.project.algorithm.practice.od2.binarysearch;

import java.util.Arrays;

/**
 * 34. 在排序数组中查找元素的第一个和最后一个位置
 *
 * 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
 * 如果数组中不存在目标值 target，返回 [-1, -1]。
 * 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
 */
public class Leetcode34 {
    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[2];
        Arrays.fill(res,-1);
        int left = 0;
        int right = nums.length-1;
        while(left<=right){
            int middle = (left+right)/2;
            if(nums[middle]==target){
                int begin = middle;
                int end = middle;
                while(begin>0 && nums[begin-1]==target){
                    begin--;
                }
                while(end<nums.length-1 && nums[end+1]==target){
                   end++;
                }
                res[0]=begin;
                res[1]=end;
                break;
            }else if(nums[middle]>target){
                right = middle-1;
            }else{
                left = middle+1;
            }
        }
        return res;
    }
}
